package com.wdc.binarytree;

import java.util.LinkedList;

/**
 * 验证二叉搜索树 98
 */
@SuppressWarnings("all")
public class E05Leetcode98 {

    public boolean isValidBST(TreeNode root) {
        //遍历
        TreeNode node = root;
        long pre = Long.MIN_VALUE;
        LinkedList<TreeNode> stack = new LinkedList<>();
        while (node != null || !stack.isEmpty()){
            if (node != null){
                stack.push(node);
                node = node.left;
            }else {
                //弹栈
                TreeNode pop = stack.pop();
                //处理值
                if (pre >= pop.val){
                    return false;
                }
                pre = pop.val;
                node = pop.right;
            }
        }
        return true;
    }

    /**
     * 递归方法来做
     * @param root
     * @return
     */
    long pre = Long.MIN_VALUE;
    public boolean isValidBST2(TreeNode root) {

        if (root == null){
            return true;
        }

        boolean a = isValidBST2(root.left);
        //处理值
        if (pre >= root.val){
            return false;
        }
        pre = root.val;
        boolean b = isValidBST2(root.right);
        return a && b;
    }


    //递归减支版本
    public boolean isValidBST3(TreeNode root) {

        if (root == null){
            return true;
        }

        boolean a = isValidBST2(root.left);
        if(!a){
            return false;
        }
        //处理值
        if (pre >= root.val){
            return false;
        }
        pre = root.val;
        return  isValidBST2(root.right);
    }





}
